In mobile communication, compression coding for digital information about speech and images is essential for efficient use of transmission bands. Especially, expectations for speech codec (encoding and decoding) techniques widely used for mobile phones are high, and further improvement of sound quality is demanded for conventional high-efficiency coding of high compression performance.
Recently, standardization of scalable codec having a multilayer configuration is underway by, for example, ITU-T (International Telecommunication Union Telecommunication Standardization Sector) and MPEG (Moving Picture Expert Group), and more efficient and higher-quality speech codec is demanded.
The performance of speech coding technique, which has improved significantly by the basic scheme “CELP (Code Excited Linear Prediction),” modeling the vocal system of speech and adopting vector quantization skillfully, is further improved by fixed excitation techniques using a small number of pulses, such as the algebraic codebook disclosed in Non-Patent Document 1. ITU-T recommendation G.729 and ETSI (European Telecommunication Standard Institute) standard AMR (Adaptive Multi-Rate) proposes representative CELP codec using an algebraic codebook, and are widely used all over the world.
In the case of performing speech encoding using an algebraic codebook, taking into account the mutual influence between pulses forming the algebraic codebook, it is desirable to search all combinations of pulses (hereinafter “whole search”). However, when the number of pulses increases, the amount of calculations required for a search increases exponentially. By contrast with this, Non-Patent document 2 discloses, for example, partial search, pruning search and Viterbi search as algebraic codebook search methods to reduce the amount of calculations significantly and substantially maintain the performance in the case of the whole search at the same time.
Among these, especially, partial search is the simplest method providing an effect of reducing the amount of calculations significantly. Here, partial search is the method of dividing a closed loop into a plurality of smaller closed loops and performing an open-loop search in the plurality of closed loops. In this partial search, it is possible to reduce the amount of calculations significantly according to the number of divisions. Also, partial search is used in international standard schemes, and, in algebraic codebook search of ETSI standard AMR, which is the standard codec of the third-generation mobile phones, partial search is performed after dividing four pulses into two subsets.
For example, if there are four pulses having eight candidate positions, there are 84 (i.e. 4096) combinations of pulses that need to be evaluated, to search for four pulses in one closed loop. By contrast with this, ETSI standard AMR divides four pulses into two subsets of two pulses and performs a search in their closed loops individually. Therefore, the number of combinations of pulses to be evaluated in ETSI standard AMR is 2×82 (i.e. 128), which is one thirty-second of the amount of calculations in the case of the whole search. Further, evaluation in ETSI standard AMR is performed for two pulses, which are less than four pulses, so that the amount calculations is further reduced.    Non-Patent Document 1: Salami, Laflamme, Adoul, “8 kbit/s ACELP Coding of Speech with 10 ms Speech-Frame: a Candidate for CCITT Standardization”, IEEE Proc. ICASSP94, pp. II-97n    Non-Patent Document 2: T. Nomura, K. Ozawa, M. Serizawa, “Efficient pulse excitation search methods in CELP”, Proc. of the 1996 spring meeting of the Acoustic Society of Japan. 2-P-5, pp. 311-312, March. 1996